package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/6/15 22:19
 */
public class SumOfLeftLeaves_404 {

    private int sum = 0;

    public int sumOfLeftLeavesRecursion(TreeNode root) {
        // 纯递归实现
        if (root == null) return 0;
        // 当左子树为叶子结点，还需要加上右子树中的所有左子节点的值
        if (isLeaf(root.left)) return root.left.val + sumOfLeftLeavesRecursion(root.right);
        return sumOfLeftLeavesRecursion(root.left) + sumOfLeftLeavesRecursion(root.right);
    }

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        sumOfLeftLeavesRoot(root);
        return sum;
    }

    public void sumOfLeftLeavesRoot(TreeNode root) {
        if (root == null) return;
        // 判断左子树是否为叶子结点，是的话将值加到sum中
        if (isLeaf(root.left)) sum += root.left.val;
        // 对左右子树分别执行递归
        sumOfLeftLeavesRoot(root.left);
        sumOfLeftLeavesRoot(root.right);
    }

    private boolean isLeaf(TreeNode leaf) {
        return leaf != null && leaf.left == null && leaf.right == null;
    }
}
